public class MaxSubArray {
    // leetcode 最大子数组和
    // https://leetcode.cn/problems/maximum-subarray/description/?envType=study-plan-v2&envId=top-100-liked
    public int maxSubArray1(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = nums[0];
        int ret = nums[0];
        for (int i = 1; i < n; i++) {
            dp[i] = Math.max(dp[i-1]+nums[i], nums[i]);
            ret = Math.max(ret, dp[i]);
        }
        return ret;
    }

    // 贪心
    public int maxSubArray(int[] nums) {
        int sum = -0x3f3f3f3f, maxSum = -0x3f3f3f3f;
        for (int n : nums) {
            sum = Math.max(sum + n, n);
            maxSum = Math.max(sum, maxSum);
        }
        return maxSum;
    }

    public static void main(String[] args) {
        MaxSubArray maxSubArray = new MaxSubArray();
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println(maxSubArray.maxSubArray(nums));
    }
}
